package com.hyper_yang.algorithmRecord;

import java.util.Arrays;

public class LeetCode_31 {
    // 思路: 从后往前找到升序子序列，确认调整子序列的最高位，剩余部分升序排列
    public static void nextPermutation(int[] nums) {
        int n = nums.length;

        int k = n - 2;
        while (k >= 0 && nums[k] >= nums[k+1])
            k--; // 找到需要调整部分的最高位
        if (k == -1) { // 不存在升序子序列
            Arrays.sort(nums);
            return;
        }
        // 找替换的数 i-1
        int i = k + 2;
        while ( i < n && nums[i] > nums[k] ) i++;

        // 交换 i-1 和 k
        int temp = nums[k];
        nums[k] = nums[i-1];
        nums[i-1] = temp;

        // 剩余部分升序
        int start = k + 1;
        int end = n - 1;
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        nextPermutation(nums);
        for (int num : nums) {
            System.out.print(num + "\t");
        }
    }
}
